/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/sequence-construction
   @Language: C++
   @Datetime: 19-06-10 16:07
   */

// Method 1, Topological Sort, Time O(n*k), Space(m+n), Time 322ms
class Solution {
public:
	/**
	 * @param org: a permutation of the integers from 1 to n
	 * @param seqs: a list of sequences
	 * @return: true if it can be reconstructed only one or false
	 */
	bool sequenceReconstruction(vector<int> &org, vector<vector<int> > &seqs) {
		// write your code here
		unordered_map<int,unordered_set<int> > graph;
		unordered_map<int,int> indegrees, pos;
		for(int i=org.size(); i--; pos[org[i]]=i);
		for(const auto &seq:seqs){
			if(seq.size()==0) continue;
			for(int i=1; i<seq.size(); ++i){
				if(graph.count(seq[i-1]) && graph[seq[i-1]].count(seq[i])) continue;
				graph[seq[i-1]].insert(seq[i]);
				++indegrees[seq[i]];
			}
			if(indegrees.count(seq[0])==0) indegrees[seq[0]]=0;
		}
		queue<int> que;
		for(const auto &node:indegrees)
			if(node.second==0) que.push(node.first);
		int size=0;
		for(; que.size()==1; ++size, que.pop()){
			for(const auto &n:graph[que.front()]){
				if(pos[que.front()]>=pos[n]) return false;
				--indegrees[n];
				if(indegrees[n]==0) que.push(n);
			}
		}
		return size==org.size();
	}
};

// Method 2, Time O(n*k), Space O(m+n), Time 235ms
class Solution {
public:
	/**
	 * @param org: a permutation of the integers from 1 to n
	 * @param seqs: a list of sequences
	 * @return: true if it can be reconstructed only one or false
	 */
	bool sequenceReconstruction(vector<int> &org, vector<vector<int> > &seqs) {
		// write your code here
		unordered_map<int,int> pos, pre;
		for(int i=org.size(); i--; pos[org[i]]=i);
		for(const auto &seq:seqs){
			for(int i=0; i<seq.size(); ++i){
				if(pos.count(seq[i])==0) return false;
				if(i && pos[seq[i-1]]>=pos[seq[i]]) return false;
				if(pre.count(seq[i])==0) pre[seq[i]]=i?pos[seq[i-1]]:-1;
				else pre[seq[i]]=max(pre[seq[i]],i?pos[seq[i-1]]:-1);
			}
		}
		for(int i=0; i<org.size(); ++i)
			if(pre[org[i]]!=i-1) return false;
		return true;
	}
};
